import java.util.HashMap;
import java.util.Map;

public class Code1 {
    // 最长的斐波那契子序列

    public int lenLongestFibSubseq(int[] arr) {
        // 创建 dp 表
        // 初始化
        // 填表
        // 确定返回值

        // 看到题目，先根据经验描述出一个状态表示
        // dp[i] 表示：以 i 位置为结尾的所有子序列中，最长的斐波那契序列的长度
        // 通常，对于子序列问题，就是通过 0 ~ i - 1 位置的值，即 j 。通过 dp[j] 来修改 dp[i] 中的内容以达到目的
        // 只有一个元素 dp[i] 是写不出来状态转移方程的

        // 当发现以 1 个元素为结尾不能解决问题时，我们可以尝试通过 2 个元素。
        // dp[i][j] 表示：以 i 位置和 j 位置结尾的所有子序列中，最长的斐波那契序列的长度
        // 此时我们可以发现，根据两个数据可以得出 x = j - i (j 的位置在 i 之后)。y = i - x 以此类推。。。
        // 通过两个元素就可以推出整个序列的情况

        // 优化操作：要获取到一个子序列，是需要多次遍历数组的，这里将 下标和数据进行绑定，构成 hash 表降低时间复杂度
        Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
        int n = arr.length;
        for(int i = 0; i < n; i++){
            hash.put(arr[i], i);
        }

        // 创建出一个 二维 dp 表
        int[][] dp = new int[n][n];
        // 初始化 dp 表中的值均为 2
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                dp[i][j] = 2;
            }
        }

        int ret = 2;
        // 让 j 从 arr 中的第三个数开始
        for(int j = 2; j < n; j++){
            // 让 i 从 arr 中的第二个数开始
            for(int i = 1; i < j; i++){
                // 通过两层循环在 arr 中进行枚举
                int a = arr[j] - arr[i];
                // 这里的 a 是存在三种情况的
                // a 存在 且 a < arr[i]     可以考虑到 dp[i之前符合条件的元素][i] + 1 (这里加上的是 j 位置表示的元素)
                // a 不存在 (不做考虑)
                // a 存在 且 arr[i] < a < arr[j] (不做考虑)
                if(a < arr[i] && hash.containsKey(a)){
                    dp[i][j] = dp[hash.get(a)][i] + 1;
                }
                ret = Math.max(ret, dp[i][j]);
            }
        }
        if(ret < 3){
            return 0;
        }
        return ret;
    }
}
